package org.dslforge.aurum;

import static java.util.Collections.singleton;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.dslforge.aurum.Automata.Transition;

class Automata<Symbols, Accpet> {
	List<List<Transition<Symbols>>> transitionTable = new ArrayList<List<Transition<Symbols>>>();

	Map<Integer, Accpet> acceptStates = new HashMap<Integer, Accpet>();

	Automata(int size) {
		for (int i = 0; i < size; i++)
			newState();
	}

	int newState() {
		int state = transitionTable.size();
		transitionTable.add(new ArrayList<Transition<Symbols>>());
		return state;
	}

	int stateCount() {
		return transitionTable.size();
	}

	void setAccept(int index, Accpet accept) {
		acceptStates.put(index, accept);
	}

	void connect(int source, Symbols symbols, int destination) {
		if (!has(source) || !has(destination))
			throw new IllegalArgumentException();
		transitionTable.get(source).add(new Transition<Symbols>(symbols, destination));
	}

	private boolean has(int index) {
		return index > -1 && index < transitionTable.size();
	}

	int mergeTransitions(Automata<Symbols, ?> other) {
		int start = transitionTable.size();
		for (List<Transition<Symbols>> transitions : other.transitionTable) {
			List<Transition<Symbols>> copied = new ArrayList<Transition<Symbols>>(transitions
					.size());
			for (Transition<Symbols> transition : transitions)
				copied.add(new Transition<Symbols>(transition.symbols, transition.destination
						+ start));
			transitionTable.add(copied);
		}
		return start;
	}

	static class Transition<Symbols> {
		final Symbols symbols;

		final int destination;

		Transition(Symbols symbols, int destination) {
			this.symbols = symbols;
			this.destination = destination;
		}
	}
}

class SubsetDeterminizer {
	private Map<Set<Integer>, Integer> Dstates = new HashMap<Set<Integer>, Integer>();

	private Stack<Set<Integer>> unmarked = new Stack<Set<Integer>>();

	private Automata<CharSet, Collection<SemanticAction>> deterministic;

	private Automata<CharSet, SemanticAction> nondeterministic;

	SubsetDeterminizer(Automata<CharSet, SemanticAction> nondeterministic) {
		this.nondeterministic = nondeterministic;
		this.deterministic = new Automata<CharSet, Collection<SemanticAction>>(0);
		unmark(closure(singleton(0)));
	}

	Automata<CharSet, Collection<SemanticAction>> determinize() {
		while (!unmarked.isEmpty()) {
			Set<Integer> T = unmarked.pop();
			Alphabet alphabet = Alphabet.alphabet(nondeterministic, T);
			while (alphabet.next()) {
				Set<Integer> U = closure(alphabet.reachableStates);
				if (!Dstates.containsKey(U))
					unmark(U);
				deterministic.connect(Dstates.get(T), alphabet.symbols, Dstates.get(U));
			}
		}
		return deterministic;
	}

	private void unmark(Set<Integer> states) {
		unmarked.push(states);
		int Dstate = deterministic.newState();
		Dstates.put(states, Dstate);
		setAcceptedStates(Dstate, states);
	}

	private void setAcceptedStates(int index, Set<Integer> states) {
		Set<SemanticAction> accepts = new HashSet<SemanticAction>();
		for (Integer state : states)
			if (nondeterministic.acceptStates.keySet().contains(state))
				accepts.add(nondeterministic.acceptStates.get(state));
		if (!accepts.isEmpty())
			deterministic.acceptStates.put(index, accepts);
	}

	Set<Integer> closure(Collection<Integer> states) {
		Set<Integer> closure = new HashSet<Integer>();
		Stack<Integer> unvisited = new Stack<Integer>();
		for (Integer state : states) {
			closure.add(state);
			unvisited.add(state);
		}
		while (!unvisited.isEmpty())
			for (Transition<CharSet> transition : nondeterministic.transitionTable.get(unvisited
					.pop()))
				if (transition.symbols == CharSet.EPSILON
						&& !closure.contains(transition.destination)) {
					closure.add(transition.destination);
					unvisited.push(transition.destination);
				}
		return closure;
	}
}

class HopcroftMinimizer {
	private Automata<CharSet, Collection<SemanticAction>> original, reversed;

	private List<Set<Integer>> workingList = new ArrayList<Set<Integer>>();

	List<Set<Integer>> partitions = new ArrayList<Set<Integer>>();

	public HopcroftMinimizer(Automata<CharSet, Collection<SemanticAction>> deterministic) {
		original = deterministic;
		makeReversedDFA();
		makeInitialPartitions();
	}

	private void makeInitialPartitions() {
		Set<Integer> notAccepted = new HashSet<Integer>();
		Set<Integer> accepted = new HashSet<Integer>();
		for (Integer state = 0; state < original.stateCount(); state++)
			(original.acceptStates.containsKey(state) ? accepted : notAccepted).add(state);
		if (notAccepted.size() > 0)
			partitions.add(notAccepted);
		if (accepted.size() > 0)
			partitions.add(accepted);
	}

	private void makeReversedDFA() {
		reversed = new Automata<CharSet, Collection<SemanticAction>>(original.stateCount());
		for (int i = 0; i < original.stateCount(); i++)
			for (Transition<CharSet> transition : original.transitionTable.get(i))
				reversed.connect(transition.destination, transition.symbols, i);
	}

	Automata<CharSet, Collection<SemanticAction>> minimize() {
		workingList.addAll(partitions);
		while (!workingList.isEmpty())
			refinePartitionsBy(workingList.remove(0));
		splitAcceptedPartition();
		return reconstructDFA();
	}

	void refinePartitionsBy(Set<Integer> set) {
		Alphabet alphabet = Alphabet.alphabet(reversed, set);
		while (alphabet.next()) {
			Set<Integer> Ia = alphabet.reachableStates;
			for (Set<Integer> R : partitions.toArray(new HashSet[partitions.size()]))
				if (!Collections.disjoint(R, Ia) && !Ia.containsAll(R)) {
					List<Set<Integer>> newPartitions = partition(R, Ia);
					Set<Integer> R1 = newPartitions.get(0);
					Set<Integer> R2 = newPartitions.get(1);
					replace(partitions, R, R1, R2);
					if (workingList.contains(R))
						replace(workingList, R, R1, R2);
					else
						workingList.add(R1.size() <= R2.size() ? R1 : R2);
				}
		}
	}

	private void replace(List<Set<Integer>> list, Set<Integer> original, Set... newPartitions) {
		list.remove(original);
		for (Set<Integer> newSet : newPartitions)
			list.add(newSet);
	}

	private List<Set<Integer>> partition(Set<Integer> lhs, Set<Integer> rhs) {
		List<Set<Integer>> result = new ArrayList<Set<Integer>>(2);
		result.add(new HashSet<Integer>());
		result.add(new HashSet<Integer>());
		for (Integer state : lhs)
			result.get(rhs.contains(state) ? 0 : 1).add(state);
		return result;
	}

	private void splitAcceptedPartition() {
		for (int i = 0; i < partitions.size(); i++) {
			Map<Collection<SemanticAction>, Set<Integer>> newPartitions = new HashMap<Collection<SemanticAction>, Set<Integer>>();
			for (Integer state : partitions.get(i))
				if (original.acceptStates.containsKey(state)) {
					Set<Integer> newPartition = newPartitions.get(original.acceptStates.get(state));
					if (newPartition == null) {
						newPartition = new HashSet<Integer>();
						newPartitions.put(original.acceptStates.get(state), newPartition);
					}
					newPartition.add(state);
				}
			if (newPartitions.size() > 1) {
				Iterator<Set<Integer>> newPartitionItr = newPartitions.values().iterator();
				Set<Integer> replace = newPartitionItr.next();
				partitions.set(i, replace);
				while (newPartitionItr.hasNext())
					partitions.add(newPartitionItr.next());
			}
		}
	}

	private Automata<CharSet, Collection<SemanticAction>> reconstructDFA() {
		List<Integer> representatives = chooseRepresentatives();
		Automata<CharSet, Collection<SemanticAction>> automata = new Automata<CharSet, Collection<SemanticAction>>(
				representatives.size());
		for (Integer state : representatives) {
			for (Transition<CharSet> transition : original.transitionTable.get(state))
				automata.connect(indexOf(state), transition.symbols,
						indexOf(transition.destination));
			if (original.acceptStates.containsKey(state))
				automata.acceptStates.put(indexOf(state), original.acceptStates.get(state));
		}
		return automata;
	}

	private int indexOf(int state) {
		for (int i = 0; i < partitions.size(); i++)
			if (partitions.get(i).contains(state))
				return i;
		throw new RuntimeException("shit happens!");
	}

	private List<Integer> chooseRepresentatives() {
		int startPartition = -1;
		List<Integer> representatives = new ArrayList<Integer>(partitions.size());
		for (int i = 0; i < partitions.size(); i++) {
			int representative = -1;
			for (Integer state : partitions.get(i)) {
				if (representative == -1 || representative != 0)
					representative = state;
				if (state == 0)
					startPartition = i;
			}
			representatives.add(representative);
		}
		representatives.set(startPartition, representatives.set(0, representatives
				.get(startPartition)));
		partitions.set(startPartition, partitions.set(0, partitions.get(startPartition)));
		return representatives;
	}
}